package LeetCodeHot100TopInterview;

public class Q098_ValidBST {

    //验证二叉搜索树
    //info: 左边是二叉搜索树 右边是二叉搜索树 我是二叉搜索树
    class Info {
        //是不是 BST
       boolean isBST;
       // 子树最大值
       int max;
       int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }
    public boolean isValidBST(TreeNode root) {
        if (root == null){
            return true;
        }
        return process(root).isBST;
    }

    //太菜了
    public Info process(TreeNode root){
        if (root.left == null && root.right == null){
            return new Info(true, root.val, root.val);
        }

        Info leftInfo = null;
        if (root.left != null){
            leftInfo = process(root.left);
        }
        Info rightInfo = null;
        if (root.right != null){
            rightInfo = process(root.right);
        }

        //全局更新的方式跑
        int max = root.val ;
        int min = root.val ;
        boolean LisBST = true; // left/rightInfo == null ==> true
        boolean RisBST = true;
        if (leftInfo != null){
            max = Math.max(max,leftInfo.max) ;
            min = Math.min(min,leftInfo.min);
            LisBST = leftInfo.isBST;
        }
        if (rightInfo != null){
            max = Math.max(max,rightInfo.max) ;
            min = Math.min(min,rightInfo.min);
            RisBST = rightInfo.isBST;
        }


        boolean isBST =
                LisBST && RisBST
                && (leftInfo == null || root.val > leftInfo.max)
                && (rightInfo == null || root.val < rightInfo.min);

        return new Info(isBST, max, min);

    }

    public static void main(String[] args) {
        Q098_ValidBST fun = new Q098_ValidBST();
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(fun.isValidBST(root));
    }
}
